Steven_Meng's Blog

传送门
注意：$X_k$为位置，而$k$才是真正加进去的数。

加入的序列为$1,2,3,......$
也就是说，每次加入的数都是当前最大的。
那么我们很快就可以推出$dp$方程：
$dp[i]=max(dp[i],dp[j]+1) j<i$
$dp[i]$初始值为$1$

我们发现：插入一个数的时候，只要知道$max(dp[j]+1)$，也就是$max(dp[j])+1$，就可以完成维护。
所以，我们建立一棵维护$dp$值的$FHQTreap$，每次加入数时，取左子树$dp$最大值$+1$插入平衡树.
输出时输出根节点$dp$值即可

// luogu-judger-enable-o2
#include <bits/stdc++.h>
#define MAXN 1000005
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
int a[MAXN];
namespace FHQTreap{
    struct node{
        int l,r;
        int val;//dp值 
        int pri;//优先级（随机生成）
        int id;//下标
        int sz;
    }tree[MAXN];
    #define lc(i) tree[i].l
    #define rc(i) tree[i].r
    int tot;
    inline void Update(int x){
        tree[x].sz=tree[lc(x)].sz+tree[rc(x)].sz+1;
        tree[x].val=max(max(tree[lc(x)].val,tree[rc(x)].val),a[tree[x].id]);
    }
    inline int New(int v,int id){
        a[id]=v;
        tree[++tot].val=v,tree[tot].pri=rand(),tree[tot].sz=1,tree[tot].id=id;
        return tot;
    }
    int Merge(int x,int y){
        if (!x||!y) return x+y;
        if (tree[x].pri<tree[y].pri){
            rc(x)=Merge(rc(x),y),Update(x);
            return x;
        }
        else{
            lc(y)=Merge(x,lc(y)),Update(y);
            return y;
        }
    }
    void Split(int i,int k,int &x,int &y){
        if (!i) {
            x=y=0;
        }
        else {
            if (tree[lc(i)].sz>=k) {y=i,Split(lc(i),k,x,lc(i));}
            else {x=i,Split(rc(i),k-tree[lc(i)].sz-1,rc(i),y);}
            Update(i);
        }
    }
    int root;
    #undef lc
    #undef rc
}
using namespace FHQTreap;
int main(){
    int n=read();
    for (register int i=1;i<=n;++i){
        int pos=read();
        int x=0,y=0;
        Split(root,pos,x,y);
        x=Merge(x,New(tree[x].val+1,i));
        root=Merge(x,y);
        printf("%d\n",tree[root].val);
    }
}